home *** CD-ROM | disk | FTP | other *** search
/ Eagles Nest BBS 8 / Eagles_Nest_Mac_Collection_Disc_8.TOAST / Developer Tools⁄Additions / IntermediatC / Linked List #11 / Linked List.c next >
C/C++ Source or Header  |  1990-11-15  |  5KB  |  167 lines
  1. /*
  2.  
  3. LINKED LIST
  4.  
  5. Write a program similar exactly the same as queue except the following:
  6.  
  7. the ships will be stored in a circular linked list (see the structure below)
  8.  
  9. typedef struct ship_type
  10.    {
  11.    int hull_number;
  12.    struct ship_type * next;
  13.    } ship_type;
  14.  
  15. A pointer tail will point to the last ship in the list.  Each ship points to
  16. the next in the list using the pointer next variable.  The last element of the
  17. list points to the head of the list.  When a ship arrives, it is added to the 
  18. end of the list.  When one is serviced, it is removed from the head of the list.
  19.  
  20. There is no size limit.
  21. Assume that any memory allocation is successful (do not check malloc)
  22. Make sure that the memory for an element if freed when it is removed from the list
  23.  
  24. Use the following procedures:
  25.     simulation            as in queue.c
  26.     add_on                add a ship to the linked list
  27.     take_off            remove a ship from the list
  28.     display_list        display the hull numbers in the list from head to tail
  29.  
  30. please note:  special conditions will have to be made for adding a ship when
  31. the list is empty, and removing a ship when only 1 ship is in the list.
  32.  
  33. */
  34.  
  35.  
  36. /* ------------------------------------------------------------------------------- */
  37.  
  38.  
  39. #include <stdio.h>
  40. #include <string.h>
  41. #include <stdlib.h>
  42.  
  43.  
  44. #define MAX_ARRIVAL        12        /* maximum arrival interval */
  45. #define MAX_SERVICE        24        /* maximum service interval */
  46. #define TIME_LIMIT        100        /* run of simulation (0 to TIME_LIMIT) */
  47. #define random(x)        (rand() % (x))
  48.  
  49.  
  50. typedef struct ship_type
  51.    {
  52.    int hull_number;
  53.    struct ship_type * next;
  54.    } ship_type;
  55.    
  56.    
  57. static void simulation (void);        /* called by main TIME_LIMIT times */
  58. static void add_on (void);            /* adds ship to linked list */
  59. static void take_off (void);        /* removes by changing head */
  60. static void display_list (void);    /* lists ships in linked list, followed by newline */
  61.  
  62.  
  63. static ship_type * tail = NULL;
  64. static int clock;                /* clock goes from 0 to TIME_LIMIT */
  65. static int arrival;                /* next arrival interval */
  66. static int service;                /* next service interval */
  67. static FILE * file_stream;        /* file control block pointer */
  68. static int new_number = 101;    /* hull numbers for newly created ships */
  69.  
  70.  
  71. /* ------------------------------------------------------------------------------- */
  72.  
  73.  
  74. main()
  75.    {
  76.    file_stream = fopen("ship list.out", "w");
  77.    arrival = random(MAX_ARRIVAL);
  78.    service = random(MAX_SERVICE);
  79.    for (clock = 0; clock < TIME_LIMIT; clock++)
  80.       simulation();
  81.    fclose(file_stream);
  82.    }
  83.  
  84.  
  85. /* ------------------------------------------------------------------------------- */
  86.  
  87.  
  88. static void simulation (void)
  89.    {
  90.    if (!arrival--)            /* check if an arrival occurred and decrement arrival */
  91.       {
  92.       add_on();                /* if arrival, add ship */
  93.       while (!(arrival = random(MAX_ARRIVAL)))
  94.          add_on();            /* loop while arrival time is 0 */
  95.       display_list();
  96.       }
  97.    if (!service--)            /* check if service and decrement service */
  98.       {
  99.       take_off();            /* if service, remove ship */
  100.       while (!(service = random(MAX_SERVICE)))
  101.          take_off();        /* loop while service time is 0 */
  102.       }
  103.    }
  104.  
  105.  
  106. /* ------------------------------------------------------------------------------- */
  107.  
  108.  
  109. static void add_on(void)
  110.    {
  111.    ship_type *new_ship;
  112.    
  113.    new_ship = (ship_type *) malloc(1 * sizeof(ship_type));    /* allocate memory for ship */
  114.    new_ship->hull_number = new_number++;                    /* create ship number */
  115.    if (!tail)                                /* if linked list is empty */
  116.       {
  117.       tail = new_ship;                        /* set first element in linked list */
  118.       tail->next = tail;                    /* to point to itself */
  119.       }
  120.    else                                        /* if at least 1 element on linked list */
  121.       {
  122.       new_ship->next = tail->next;            /* newest ship points to head */
  123.       tail->next = new_ship;                /* last element points to newest element */
  124.       tail = new_ship;                        /* tail pointer now points to newest element */
  125.       }                                        /* since this is now the last element */
  126.    }
  127.  
  128.  
  129. /* ------------------------------------------------------------------------------- */
  130.  
  131.  
  132. static void take_off(void)
  133.    {
  134.    ship_type * delete;
  135.    
  136.    if (!tail)                    /* if no elements, do nothing */
  137.       return;
  138.    if (tail->next == tail)        /* if only 1 element in list */
  139.       {
  140.       free(tail);                /* release memory for the element */
  141.       tail = NULL;                /* force pointer to point to NULL */
  142.       }
  143.    else                            /* if more than 1 element */
  144.       {
  145.       delete = tail->next;        /* temp pointer points to first element */
  146.       tail->next = tail->next->next;    /* last element points to 2nd element */
  147.       free(delete);                /* free memory used by first element */
  148.       }                            /* now, second element is first element */
  149.    }
  150.  
  151.  
  152. /* ------------------------------------------------------------------------------- */
  153.  
  154.  
  155. static void display_list(void)
  156.    {
  157.    ship_type * list;
  158.  
  159.    list = tail->next;        /* looping pointer points to head of linked list */
  160.    while (list != tail)        /* do until the pointer reaches the last element */
  161.       {
  162.       fprintf(file_stream, "%4d\n", list->hull_number);    /* print element hull number */
  163.       list = list->next;    /* have pointer point to next element */
  164.       }
  165.    fprintf(file_stream, "%4d\n\n", list->hull_number);    /* print last element hull number */
  166.    }                                                    /* followed by an extra return */
  167.